package com.wkq.selectionsort;

import com.wkq.Sort;
import com.wkq.util.ArrayGenerator;
import com.wkq.util.SortingHelper;

/**
 * 初始状态：arr[0...n)未排序
 * 外层循环执行操作：arr[i,n)中的最小值要放到arr[i]的位置
 * 内存循环执行操作：找出arr[i,n)中最小值的索引 minIndex
 * 循环不变量：arr[i...n)未排序，arr[0...i)已排序
 * 选择排序法的复杂度分析：
 *  1+2+3+...+n
 *  =(1+n)*n/2
 *  =(1/2)*n^2+(1/2)n
 *  O(n^2)
 */
public enum SelectionSort implements Sort {
    INSTANCE;

    @Override
    public <E extends Comparable<E>> void sort(E[] arr) {
        //循环不变量 arr[0,i)已排序，arr[i,n)未排序
        for (int i = 0; i < arr.length; i++) {
            int minIndex = i;
            //选择arr[i...n)中最小值的索引
            for (int j = i + 1; j < arr.length; j++) {
                minIndex = arr[j].compareTo(arr[minIndex]) < 0 ? j : minIndex;
            }
            SortingHelper.swap(arr, i, minIndex);
        }
    }

    public static void main(String[] args) {
        int[] dataSize = {10000, 100000};
        for (int n : dataSize) {
            Integer[] arr = ArrayGenerator.generatorRandomArray(n, n);
            SortingHelper.sortTest(SelectionSort.INSTANCE, arr);
        }
    }

}
